package com.future.offer;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Set;

/**
 * Description: 剑指 Offer 49. 丑数
 * <p>
 * 我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
 * <p>
 * 1 <= n <= 1690
 * <p>
 * 输入: n = 10
 * 输出: 12
 * 解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
 *
 * @author weiruibai.vendor
 * Date: 2023/1/29 10:44
 */
public class Solution_49 {

    private static Solution_49 instane = new Solution_49();

    public static void main(String[] args) {

        int n = 10;
        /*n = 14;
        n = 151;
        n = 1690;*/
        System.out.println(instane.nthUglyNumber(n));
        System.out.println(instane.nthUglyNumber_v2(n));
        System.out.println("==========");
       /* for (int i = 1500; i <= 1700; i++) {
            System.out.println(i + "====>" + instane.nthUglyNumber(i));
        }*/
    }

    /**
     * @param n
     * @return
     */
    public int nthUglyNumber_v2(int n) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        Set<Integer> repeat = new HashSet<>();
        queue.add(1);
        List<Integer> list = new ArrayList<>();
        list.add(2);
        list.add(3);
        list.add(5);
        int ans = 1;
        for (int i = 0; i < n; i++) {
            ans = queue.poll();
            for (Integer num : list) {
                Long res = (long) num * ans;
                if (res >= 0 && res <= Integer.MAX_VALUE && repeat.add(res.intValue())) {
                    queue.add(res.intValue());
                }
            }
        }
        return ans;
    }

    /**
     * 超时
     *
     * @param n
     * @return
     */
    public int nthUglyNumber(int n) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        Set<Integer> repeat = new HashSet<>();
        Set<Integer> hasCalcRepeat = new HashSet<>();
        queue.add(1);
        List<Integer> list = new ArrayList<>();
        list.add(2);
        list.add(3);
        list.add(5);
        PriorityQueue<Integer> tmp;
        for (int i = 0; i < n; i++) {
            tmp = new PriorityQueue<>();
            while (!queue.isEmpty()) {
                Integer poll = queue.poll();
                tmp.add(poll);
                if (!hasCalcRepeat.add(poll)) {
                    continue;
                }
                for (Integer num : list) {
                    Long res = (long) num * poll;
                    if (res >= 0 && res <= Integer.MAX_VALUE && !repeat.contains(res.intValue())) {
                        tmp.add(res.intValue());
                        repeat.add(res.intValue());
                    }
                }
            }
            queue = tmp;
        }
        int ans = 1;
        int i = 0;
        while (i < n) {
            ans = queue.poll();
            // System.out.println(ans);
            i++;
        }
        return ans;
    }
}
